package com.njupt.DynamicProgramming;

/**
 * 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
 *你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
 */
public class MinCostClimbingStairs {

    /**
     *1、DP数组，dp[i]表示到达第i阶台阶所要花费的最少成本
     * 2、递推公式 dp[i] =min( dp[i-1] + cost[i-1] , dp[i-2] + cost[i-2] )
     * 3、dp数组初始化:因为一开始的起始位子可能式0，可能是1，表示一开始的时候不花费力气
     * 4、遍历方向从后往前
     * @param cost
     * @return
     */
    public int minCostClimbingStairs(int[] cost) {

        if(cost.length ==2){
            return Math.min(cost[0],cost[1]);
        }
        int[] dp = new int[cost.length+1];
        dp[0] = 0;
        dp[1] = 0;
        dp[2] = Math.min(cost[0],cost[1]);
        for (int i = 3; i <dp.length ; i++) {
            dp[i] = Math.min( dp[i-1] + cost[i-1] ,dp[i-2] + cost[i-2] );
        }
        return dp[dp.length-1];
    }

    public int minCostClimbingStairs1(int[] cost){
        int minCost = 0;
        int index = cost.length;


        while (true){
            if(cost[index-1]<cost[index-2]){
                minCost += cost[index-1];
                index = index - 1;
            }else {
                minCost += cost[index-2];
                index = index -2;
            }
            if(index == 0 || index == 1){

                break;
            }
        }
        return minCost;

    }

    public static void main(String[] args) {
        int[] costs = {0,2,2,1};
        MinCostClimbingStairs test = new MinCostClimbingStairs();
        int minCost = test.minCostClimbingStairs1(costs);
        System.out.println(minCost);
    }
}
